A parallel computer includes a plurality of nodes that are information processing apparatuses to perform computing, and a plurality of switches that constructs a network between the nodes. In the description below, a node of a parallel computer refers to an information processing apparatus to perform computing, unless otherwise stated.
FIG. 1 illustrates a configuration diagram of a parallel computer including nodes and switches.
In FIG. 1, as an example of a network topology of a parallel computer, a 4×4 two-dimensional mesh topology in which nodes are arranged two dimensionally, the horizontal direction is assumed as X axis, the vertical direction is assumed as Y axis, and the bottom left of FIG. 1 is assumed as the origin. As illustrated in FIG. 1, each node n00-n33 is connected to a corresponding switch s00-s33. In addition, each switch s00-s33 is connected to switches that are adjacent in the X axis direction and the Y axis direction, among the switches s00-s33. The network between nodes in the parallel computer is constituted as described above.
There are a plurality of communication routes between two nodes in some network topologies of the parallel network.
FIG. 2 is a diagram illustrating a 4×4 two-dimensional mesh topology of a parallel computer. For example, in the 4×4 two-dimensional mesh topology of a parallel computer illustrated in FIG. 2, in a case in which a node n03 for which (x, y)=(0, 3) performs communication to a node n30 for which (x, y)=(3, 0), there are 20 patterns of routes even when those with 6 hops, the minimum number of hops, are counted.
Methods for selecting a route from a plurality of routes include source routing and dimension order routing.
Source routing is a method in which a node that transmits a packet determines a route that the packet goes through, and specifies the route for the packet. The source routing includes strict source routing and loose source routing. In the strict source routing, a node that transmits a packet specifies all the routes that the packet goes through. In the loose source routing, because when all the routes are specified as in the strict source routing, the packet header becomes large, a node that transmits a packet specifies a part of routes that the packet goes through, and a route determines the rest of routes according to dimension order routing and the like.
The dimension order routing is a method in which the address of each dimension (each coordinate axis) is adjusted to the communication partner node in a predetermined order. For example, in the two dimensional topology illustrated in FIG. 2, there are two patterns of dimension order routing. That is, there are a method in which the address of the X axis is adjusted first, and the address of the Y axis is adjusted next (dimension order routing in X axis, Y axis order), and a method in which the address of the Y axis is adjusted first and the address of the X axis is adjusted next (dimension order routing in Y axis, X axis order).
It is important in the performance aspect of the parallel computer which route is used among a plurality of routes for communication.
FIG. 3 is a diagram illustrating an example of routing in a case in which congestion occurs in a plurality of communication routes. FIG. 4 is a diagram illustrating an example of routing in a case in which congestion is not occurring in a plurality of communication routes. FIG. 3 and FIG. 4 respectively illustrate an example in which the node n03 performs communication c1 to the node n30, the node n13 performs communication c2 to the node n31, and the node n23 performs communication c3 to the node 32. In the dimension order routing in X axis, Y axis order illustrated in FIG. 3, the communications c1-c3 between the respective nodes concentrate on particular link, causing congestion in the particular link. On the other hand, in the dimension order routing in Y axis, X axis, order illustrated in FIG. 4, since the communications c1-c3 between the respective nodes do not concentrate on any particular link, no congestion is occurring in the routes.
Therefore, there is a need for a routing method for preventing communication between respective nodes from concentrating on particular link and causing congestion in the particular route. Specifically, there is a need for a routing method in which an optimal route is selected according to the communication status of the routes. The routing method in which the route is switched dynamically according to the communication status of the routes is called adaptive routing, and several methods have been proposed as conventional art.
As conventional art of the routing method in which an optimal route is selected according to the communication status of the routes, there is a method in which the transmission latency of a message in the communication between nodes is measured, and the route between the nodes is changed based on the transmission latency. The specific steps of the routing are as follows.
(1) In a local node, a set of routes to a remote node is created. Here, the local node refers to the node on the side that is requesting the communication in the communication between the nodes. Meanwhile, the remote node refers to the node on the side that is receiving the communication request from the local node in the inter-node communication.
(2) The local node transmits a message to a remote node via each route included in the created set of routes, and measures the latency until the message reaches the remote node. The measurement of the latency is performed by adding the latency in a field of the message in the switches that the message goes through, and sending back the latency to the local node when it reaches the remote node.
(3) Based on the measured latency, the latency for all the routes included in the set of routes is calculated, and the route with a latency that is equal to or smaller than a threshold value is added to the set of routes. The route with a latency that exceeds the threshold value is eliminated from the set of routes.
(4) The local node selects the route for the transmission message from the set of routes. As the way of selection, one with smaller latency is selected with priority.
(5) Thereafter, returning to (2) above, the latency measurement, creation of the set of routes, and the route selection are repeated.